package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class M90SubSetsII {

    private List<List<Integer>> res = new LinkedList<>();
    private LinkedList<Integer> trace = new LinkedList<Integer>();

    private boolean in = true;

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

        backtrack(nums, 0);

        return res;
    }

    private void backTracking(int[] nums, int start) {
        res.add(new ArrayList<>(trace));


        for (; start < nums.length; start++) {
            if(!in && start>0&&nums[start]==nums[start-1]){
//                start++;
                continue;
            }

            in =true;

            // 做选择
            trace.add(nums[start]);
            backTracking(nums,start+1);


            // 撤销
            trace.removeLast();
            in=false;


        }

    }

    void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(trace));

        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
//            if (i > start && nums[i] == nums[i - 1]) {
            // startindex即本层第一个数，如果下层要加的数字和本层本结点的下一个结点数字一样的话，
            // 为了不误删下层要加的数字，需要增设这个判断条件。你可以把该判断条件带入图解的1,2那个结点手算一下就明白了。
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
//              }
            }
            trace.addLast(nums[i]);
            backtrack(nums, i + 1);
            trace.removeLast();
        }
    }
    @Test
    public void test(){
        System.out.println(Arrays.toString(subsetsWithDup(new int[]{1,2,2}).toArray()));
        // [[],[1],[1,1],[1,1,2],[1,1,2,2],[1,2],[1,2,2],[2],[2,2]]
//        [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
    }

}
